function dist = dijkstra(Adjcency,source)
% input sourse is the index of start point 
% Adjcency is a sparse matrix in lower left corner
    dist = ones(1,size(Adjcency,1)) * inf;
    previous = ones(1,size(Adjcency,1)) * inf;
    dist(source) = 0;
    Q = 1:size(Adjcency,1);
    while size(Q,2) ~= 0
        [minV,idx] = min(dist(Q));
        u = Q(idx);
        if dist(u) == inf
            break
        end
        Q(Q == u) = [];
        neighbors = [find(Adjcency(u,:) ~= 0),find(Adjcency(:,u) ~= 0)'];
        for v = neighbors
            a = Adjcency(min(v,u),max(v,u));
            if a == 0
                a = inf;
            end
            alt = dist(u) + a;
            if alt < dist(v)
                dist(v) = alt;
                previous(v) = u;
            end
        end
    end  
end